#ifndef __FAST_INDEXED_SET_DOT_HPP__
#define __FAST_INDEXED_SET_DOT_HPP__
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
#include <map>
#include <vector>
#include <HashFunctions.hpp>
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
#ifdef __MAC_OSX__
#define U64CHAR "lld"
#else
#define U64CHAR "ld"
#endif
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
#define __DEDUP_OVERFLOW__
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
#include <memline.hpp>
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
using namespace std;
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
#define __FIS_BUCKET_STATS__
// #define __FIS_DEBUG_COMPILE__
// #define __FIS_INLINE_COUNTS__
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
// -- debug stuff --
#ifdef __FIS_DEBUG_COMPILE__
#include <iostream>
#include <assert.h>
#define DEBUG_ASSERT( x ) assert( x )
using namespace std;
#else
#define DEBUG_ASSERT( x )
#endif
// -- end debug stuff --
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
#define MIN( a, b ) (( a < b ) ? a : b )
#ifdef __FIS_ZSIM__
typedef volatile uint32_t fis_lock_t;
#define FREE   gm_free
#define CALLOC gm_calloc
#else
typedef pthread_mutex_t fis_lock_t;
#define FREE( x )   { if( x ) { free( x ); x = NULL; } }
#define CALLOC calloc
#define info( ... )   printf( __VA_ARGS__ ); printf( "\n" ); fflush( stdout ); fflush( stderr );
#endif
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
#define __FAST_INDEXED_SET_COMPILE_FOR_FINE_GRAINED_LOCKS__
#define LOCK_INIT_FUNC( x, y ) pthread_mutex_init   ( x, y )
#define LOCK_FUNC( x )         pthread_mutex_lock   ( x )
#define UNLOCK_FUNC( x )       pthread_mutex_unlock ( x )
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
#include <HashFunctions.hpp>
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
void * AllocAlign( const uint64_t numBytes, const char * memname );
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
class multi_word {
    const uint32_t numWords;
    uint64_t * words;
public:
    multi_word( const uint32_t _numWords, const uint64_t * src ) : numWords( _numWords ) {
        words = NULL;
        words = new uint64_t[ numWords ];
        assert( words );
        for( uint32_t i = 0; i < numWords; i++ ) {
            words[i] = src[i];
        }
    }
    multi_word( const multi_word & src ) : numWords( src.NumWords() ) {
        words = NULL;
        words = new uint64_t[ numWords ];
        assert( words );
        for( uint32_t i = 0; i < numWords; i++ ) {
            words[i] = src.words[i];
        }        
    }
    ~multi_word( void ) {
        if( words ) {
            delete [] words;
        }
    }
    inline multi_word & operator = ( const multi_word & src ) {
        assert( numWords == src.NumWords() );
        for( uint32_t i = 0; i < numWords; i++ ) {
            words[i] = src.words[i];
        }
        return *this;
    }
    uint64_t * RawPtr( void ) const {
        return words;
    }
    inline uint32_t NumWords( void ) const { return numWords; }
    inline const bool operator <  ( const multi_word & other ) const {
        assert( numWords == other.NumWords() );
        for( uint32_t i = 0; i < numWords; i++ ) {
            if( words[ i ] < other.words[ i ] ) { return true;  }
            if( words[ i ] > other.words[ i ] ) { return false; }
        }
        return false;
    }
};
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
class IndexedSetBase {
protected:
    fis_lock_t glock;
    char * name;
    
    static const uint32_t maxLoad = 64;
public:
    HashWrapper * hf;
    
    void SetHash( HashWrapper * _hf );
    void SetName( const char * _name );
    inline const char * GetName ( void ) const { return name; }
    inline uint32_t MaxLoad     ( void ) const { return maxLoad; }
    
    IndexedSetBase  ( void ) { name = NULL;  }
    ~IndexedSetBase ( void ) { FREE( name ); }
};

class IndexedSet : public IndexedSetBase {
    void init( void );
protected:
    static const uint32_t lineSize      = 64;
    static const uint32_t wordSize      = 8;
    static const uint32_t keysPerBucket = 64;
    static const uint32_t wordsPerSig   = lineSize / wordSize;

    const uint32_t idxBits;
    const uint32_t wordsPerKey;
    const uint32_t bytesPerKey;
    const uint32_t bytesPerBucket;
    const uint32_t wordsPerBucket;
    const uint32_t numBuckets;

    uint32_t numEntries;
    uint32_t preLoad;
public:
    const uint64_t hashMask;
protected:
    const uint32_t numKeys;

    static const uint32_t IDX_NOT_FOUND_VAL = 0xFFFFFFFF;
    
    uint64_t * keys;
    uint64_t * sigs;
    fis_lock_t * locks;
    
    #ifdef __FIS_DEBUG_COMPILE__
    LSU * max_sig_line;
    #endif
    #ifdef  __FIS_BUCKET_STATS__
    uint32_t * load;
    #endif
    
    void LockEveryBucket( void ) const;
    void UnlockEveryBucket( void ) const;

    // shortcuts to calculate useful offsets
    // e.g. BucketOffset() takes a bucket index (from 0 to Nbuckets-1) and returns the global offset within array of keys (from 0 to Nkeys-1)
    inline uint32_t BucketOffset ( const uint32_t bucketIdx ) const { return bucketIdx * wordsPerBucket;    }
    inline uint32_t SigOffset    ( const uint32_t bucketIdx ) const { return bucketIdx * wordsPerSig;       }
    inline uint32_t WayOffset    ( const uint32_t wayIdx    ) const { return wayIdx    * wordsPerKey;       }
    inline uint32_t KeyIndex     ( const uint32_t bucketIdx, const uint32_t wayIdx ) const { return bucketIdx * keysPerBucket + wayIdx; }
    inline uint32_t WayIdxFromKeyIdx    ( const uint32_t keyIdx ) const { return keyIdx & 63; }
    inline uint32_t BucketIdxFromKeyIdx ( const uint32_t keyIdx ) const { return keyIdx >> 6; }
        
    inline uint32_t CountBucketOccupancy( const uint32_t bucketIdx ) const {
        
        uint32_t numZeroSig = 0;
        
        uint32_t wayIdx  = SigSearch( bucketIdx, 0 );
        
        while( IsValidIdx( wayIdx) ) {
            numZeroSig++;
            wayIdx = NextSigSearch( bucketIdx, 0, wayIdx );
        }
        return keysPerBucket - numZeroSig - preLoad;
    }
    inline uint32_t KeyNotFoundInsertKey( const uint64_t * k, const uint32_t bucketIdx, const unsigned char sig ) {

        uint32_t wayIdx = InsertSig( bucketIdx, sig );
        
        const uint32_t offset = BucketOffset( bucketIdx ) + WayOffset( wayIdx );

        DEBUG_ASSERT( bucketIdx < numBuckets    );
        DEBUG_ASSERT( wayIdx    < keysPerBucket );
        DEBUG_ASSERT( offset + 0           <  wordsPerKey * numKeys );
        DEBUG_ASSERT( offset + wordsPerKey <= wordsPerKey * numKeys );
        
        for( uint32_t i = 0; i < wordsPerKey; i++ ) {
            keys[ offset + i ] = k[ i ];
        }
        return KeyIndex( bucketIdx, wayIdx );
    }
    inline uint32_t SigSearch     ( const uint32_t bucketIdx, const unsigned char sig2match ) const {
        
        const uint32_t sigOffset = SigOffset( bucketIdx );
        LSU * sigline = (LSU*) &sigs[ sigOffset ];
        
        uint32_t wordOff = 0;
        for( uint32_t wordIdx = 0; wordIdx < 8; wordIdx++ ) {
            DEBUG_ASSERT( sigline < max_sig_line );
            if( sigline->bytes.b0 == sig2match ) { return wordOff + 0; }
            if( sigline->bytes.b1 == sig2match ) { return wordOff + 1; }
            if( sigline->bytes.b2 == sig2match ) { return wordOff + 2; }
            if( sigline->bytes.b3 == sig2match ) { return wordOff + 3; }
            if( sigline->bytes.b4 == sig2match ) { return wordOff + 4; }
            if( sigline->bytes.b5 == sig2match ) { return wordOff + 5; }
            if( sigline->bytes.b6 == sig2match ) { return wordOff + 6; }
            if( sigline->bytes.b7 == sig2match ) { return wordOff + 7; }
            wordOff += 8;
            sigline++;
        }
        return IDX_NOT_FOUND_VAL;
    }
    inline uint32_t NextSigSearch ( const uint32_t bucketIdx, const unsigned char sig2match, const uint32_t prev ) const {
        
        const uint32_t sigOffset = SigOffset( bucketIdx );
        LSU * sigline = (LSU*) &sigs[ sigOffset ];

        const uint32_t prevByteIdx = prev & 0x7;
        const uint32_t prevWordIdx = prev >> 3;
        uint32_t wordOff = 0;
        for( uint32_t wordIdx = 0; wordIdx < 8; wordIdx++ ) {
            DEBUG_ASSERT( sigline < max_sig_line );
            if( wordIdx > prevWordIdx ) {
                if( sigline->bytes.b0 == sig2match ) { return wordOff + 0; }
                if( sigline->bytes.b1 == sig2match ) { return wordOff + 1; }
                if( sigline->bytes.b2 == sig2match ) { return wordOff + 2; }
                if( sigline->bytes.b3 == sig2match ) { return wordOff + 3; }
                if( sigline->bytes.b4 == sig2match ) { return wordOff + 4; }
                if( sigline->bytes.b5 == sig2match ) { return wordOff + 5; }
                if( sigline->bytes.b6 == sig2match ) { return wordOff + 6; }
                if( sigline->bytes.b7 == sig2match ) { return wordOff + 7; }                
            }
            else if( wordIdx == prevWordIdx ) {
                // -- not checked -- if( 0 > prevByteIdx ) if( sigline->bytes.b0 == sig ) { return wordOff + 0; }
                if( 1 > prevByteIdx ) if( sigline->bytes.b1 == sig2match ) { return wordOff + 1; }
                if( 2 > prevByteIdx ) if( sigline->bytes.b2 == sig2match ) { return wordOff + 2; }
                if( 3 > prevByteIdx ) if( sigline->bytes.b3 == sig2match ) { return wordOff + 3; }
                if( 4 > prevByteIdx ) if( sigline->bytes.b4 == sig2match ) { return wordOff + 4; }
                if( 5 > prevByteIdx ) if( sigline->bytes.b5 == sig2match ) { return wordOff + 5; }
                if( 6 > prevByteIdx ) if( sigline->bytes.b6 == sig2match ) { return wordOff + 6; }
                if( 7 > prevByteIdx ) if( sigline->bytes.b7 == sig2match ) { return wordOff + 7; }
            }
            sigline++;
            wordOff += 8;
        }
        return IDX_NOT_FOUND_VAL;
    }
    inline uint32_t InsertSig     ( const uint32_t bucketIdx, const unsigned char sig2insert ) {

        const uint32_t sigOffset = SigOffset( bucketIdx );
        LSU * sigline = (LSU*) &sigs[ sigOffset ];
        
        const uint32_t wayIdx = SigSearch( bucketIdx, 0 );
        
        if( IsInvalidIdx( wayIdx ) ) {
            UNLOCK_FUNC( &locks[ bucketIdx ] );
            PrintBucketStats();
            fflush( stderr );
            fflush( stdout );
            fprintf( stderr, "------------------------------------------------\n" );
            fprintf( stderr, "InsertSig(): out of room\n" );
            fprintf( stderr, "InsertSig(): name = %s\n", name );
            fprintf( stderr, "------------------------------------------------\n" );
            fflush( stderr );
            fflush( stdout );
            assert( false );            
        }
        #ifdef  __FIS_BUCKET_STATS__
        load[ bucketIdx ]++;
        #endif
        
        uint32_t byteIdx = wayIdx;
        while( byteIdx > 7 ) {
            DEBUG_ASSERT( sigline < max_sig_line );
            sigline++;
            byteIdx -= 8;
        }
        DEBUG_ASSERT( sigline < max_sig_line );
        if( byteIdx == 0 ) { sigline->bytes.b0 = sig2insert; return wayIdx; }
        if( byteIdx == 1 ) { sigline->bytes.b1 = sig2insert; return wayIdx; }
        if( byteIdx == 2 ) { sigline->bytes.b2 = sig2insert; return wayIdx; }
        if( byteIdx == 3 ) { sigline->bytes.b3 = sig2insert; return wayIdx; }
        if( byteIdx == 4 ) { sigline->bytes.b4 = sig2insert; return wayIdx; }
        if( byteIdx == 5 ) { sigline->bytes.b5 = sig2insert; return wayIdx; }
        if( byteIdx == 6 ) { sigline->bytes.b6 = sig2insert; return wayIdx; }
        if( byteIdx == 7 ) { sigline->bytes.b7 = sig2insert; return wayIdx; }
        assert( false );
    }
    inline void OverwriteSig( const uint32_t bucketIdx, const uint32_t wayIdx, const unsigned char sig2write ) {

        const uint32_t sigOffset = SigOffset( bucketIdx );
        LSU * sigline = (LSU*) &sigs[ sigOffset ];

        DEBUG_ASSERT( wayIdx < 64 );
        
        uint32_t byteIdx = wayIdx;
        while( byteIdx > 7 ) {
            byteIdx -= 8;
            sigline++;
        }
        DEBUG_ASSERT( sigline < max_sig_line );
        DEBUG_ASSERT( byteIdx < 8 );
        
        if( byteIdx == 0 ) { sigline->bytes.b0 = sig2write; return; }
        if( byteIdx == 1 ) { sigline->bytes.b1 = sig2write; return; }
        if( byteIdx == 2 ) { sigline->bytes.b2 = sig2write; return; }
        if( byteIdx == 3 ) { sigline->bytes.b3 = sig2write; return; }
        if( byteIdx == 4 ) { sigline->bytes.b4 = sig2write; return; }
        if( byteIdx == 5 ) { sigline->bytes.b5 = sig2write; return; }
        if( byteIdx == 6 ) { sigline->bytes.b6 = sig2write; return; }
        if( byteIdx == 7 ) { sigline->bytes.b7 = sig2write; return; }
        assert( false );        
    }
    inline bool CheckKeyMatch( const uint64_t * k, const uint32_t bucketIdx, const uint32_t wayIdx ) const {

        const uint32_t offset = BucketOffset( bucketIdx ) + WayOffset( wayIdx );

        DEBUG_ASSERT( bucketIdx < numBuckets    );
        DEBUG_ASSERT( wayIdx    < keysPerBucket );
        DEBUG_ASSERT( offset + 0           <  wordsPerKey * numKeys );
        DEBUG_ASSERT( offset + wordsPerKey <= wordsPerKey * numKeys );

        for( uint32_t i = 0; i < wordsPerKey; i++ ) {
            if( keys[ offset + i ] != k[ i ] ) { return false; }
        }
        return true;
    }

    uint32_t FindKey( const uint64_t * k, const uint32_t bucketIdx, const unsigned char sig ) const {
        
        uint32_t wayIdx = SigSearch( bucketIdx, sig );

        while( IsValidIdx( wayIdx ) ) {
            bool keyMatch = CheckKeyMatch( k, bucketIdx, wayIdx );
            if( keyMatch ) {
                return KeyIndex( bucketIdx, wayIdx );
            }
            wayIdx = NextSigSearch( bucketIdx, sig, wayIdx );
        }
        DEBUG_ASSERT( IsInvalidIdx( wayIdx ) );
        return wayIdx;
    }

    inline const unsigned char h2sig( const uint64_t h ) const {
        uint32_t sa = 56;
        unsigned char sig = h >> sa;
        while( sig == 0 ) {
            sa -= 8;
            sig = h >> sa;
        }
        return sig;
    }
    
public:
    IndexedSet( const uint32_t _idxBits, const uint32_t _wordsPerKey );
    ~IndexedSet( void );
    
    void FreeKeysAndSigs( void );

    void PrintBucketStats( void ) const;
    double BucketOccupancyAverage( void ) const;
    double OccAvgDeltaSqSum( double avg ) const;
    double BucketOccupancyStdDev( double avg ) const;
    uint32_t BucketOccupancyMinimum ( void ) const;

    inline uint32_t NumAllocatableKeys( void ) const { return numKeys;    }
    inline uint32_t NumBuckets        ( void ) const { return numBuckets; }
    inline uint64_t size( void ) const { return uint64_t( numEntries ); }
    
    inline const bool IsValidIdx   ( const uint32_t indexVal  ) const { return indexVal != IDX_NOT_FOUND_VAL; }
    inline const bool IsInvalidIdx ( const uint32_t indexVal  ) const { return indexVal == IDX_NOT_FOUND_VAL; }
    
    inline uint32_t BucketLoad( const uint64_t * k ) const {
        const uint64_t h = hf->hash( k, wordsPerKey );
        const uint32_t bucketIdx = hashMask & h;
        #ifdef __FIS_BUCKET_STATS__
        return load[ bucketIdx ];
        #else
        return CountBucketOccupancy( bucketIdx );
        #endif
    }
    inline uint32_t BucketLoad( const uint32_t bucketIdx ) const {
        #ifdef __FIS_BUCKET_STATS__
        return load[ bucketIdx ];
        #else
        return CountBucketOccupancy( bucketIdx );
        #endif
    }
    uint32_t FindKey( const uint64_t * k ) const {
        
        const uint64_t h = hf->hash( k, wordsPerKey );
        const uint32_t bucketIdx = hashMask & h;
        const unsigned char sig  = h2sig( h );
        const uint32_t keyIdx = FindKey( k, bucketIdx, sig );
        
        return keyIdx;
    }
    bool KeyExists( const uint64_t * k ) const {
        const uint32_t keyIdx = FindKey( k );
        return IsValidIdx( keyIdx );
    }

    inline void Lock   ( void ) {   LOCK_FUNC( &glock ); }
    inline void Unlock ( void ) { UNLOCK_FUNC( &glock ); }
    inline uint32_t LockBucket( const uint64_t * k ) {

        const uint64_t h = hf->hash( k, wordsPerKey );
        const uint32_t bucketIdx = hashMask & h;
        
        LOCK_FUNC( &locks[ bucketIdx ] );
        return bucketIdx;
    }
    inline void UnlockBucket( const uint32_t bucketIdx ) {
        UNLOCK_FUNC( &locks[ bucketIdx ] );
    }
    void PreLoad( const uint32_t load ) {
        
        assert( load <= keysPerBucket );
        preLoad = load;
        
        for( uint32_t bucketIdx = 0; bucketIdx < numBuckets; bucketIdx++ ) {

            for( uint32_t wayIdx = 0; wayIdx < load; wayIdx++ ) {
                assert( wayIdx == InsertSig( bucketIdx, 1 ) );
            }
        }
    }
    void ClearPreLoad( void ) {

        for( uint32_t bucketIdx = 0; bucketIdx < numBuckets; bucketIdx++ ) {

            for( uint32_t wayIdx = 0; wayIdx < preLoad; wayIdx++ ) {
                OverwriteSig( bucketIdx, wayIdx, 0 );
            }
        }
        preLoad = 0;
    }
    
    double Load( void ) const;
};

class IndexedCounters : public IndexedSet {
    //
    // IndexedCounters:
    // ... implements a map from key to count
    // ... the count can be accessed by either the key, or its index
    // ... the index is location of the key in the hash table
    // ...
    // ... three different (reference) counts are tracked:
    // ... ... A: for all memory
    // ... ... K: for kernel memory
    // ... ... U: for user memory
    //
    uint32_t topOfOverflowIdx;
    const uint32_t topOfDedupIdx;
    
    // value size, i.e. as opposed to key size (bluntly, this implements 32bit counters)
    static const uint32_t wordsPerVal = 1;
    static const uint32_t bytesPerVal = sizeof( uint32_t );

    uint64_t a_unique;
    uint64_t k_unique;
    uint64_t u_unique;
    uint64_t a_totals;
    uint64_t k_totals;
    uint64_t u_totals;
    uint32_t * a_counts;
    uint32_t * k_counts;
    uint32_t * u_counts;
    
    uint64_t CountUnique( const uint32_t * counts ) const;
    uint64_t CountTotals( const uint32_t * counts ) const;

public:
    IndexedCounters( const uint32_t _idxBits, const uint32_t _wordsPerKey, const uint64_t _seed = 0x9ddfea08eb382d69ULL );
    ~IndexedCounters( void );

    uint32_t InsertKey( const uint64_t * k );

    uint32_t MaxCapacity( void ) const {
        return MaxLoad() * numBuckets;
    }

    void IncCountByIndex( const uint32_t keyIndex, const uint32_t arc, const uint32_t krc, const uint32_t urc ) {

        assert( keyIndex < NumAllocatableKeys() );
        assert( keyIndex < numKeys );
        
        #ifdef __FIS_INLINE_COUNTS__
        __sync_fetch_and_add( &a_count, arc );
        #endif
        __sync_fetch_and_add( &a_counts[ keyIndex ], arc );
        
        if( krc ) {
            #ifdef __FIS_INLINE_COUNTS__
            __sync_fetch_and_add( &k_count, krc );
            #endif
            __sync_fetch_and_add( &k_counts[ keyIndex ], krc );
        }
        if( urc ) {
            #ifdef __FIS_INLINE_COUNTS__
            __sync_fetch_and_add( &u_count, urc );
            #endif
            __sync_fetch_and_add( &u_counts[ keyIndex ], urc );
        }
    }
    
    // interface to the counts:
    // ... AKU    => (A)ll, (K)ernel, and (U)ser
    // ... Total  => Total reference count
    // ... Unique => Count of unique keys
    void AccumCounts( void );
    inline uint64_t AUnique( void ) const { return a_unique; }
    inline uint64_t KUnique( void ) const { return k_unique; }
    inline uint64_t UUnique( void ) const { return u_unique; }
    inline uint64_t ATotals( void ) const { return a_totals; }
    inline uint64_t KTotals( void ) const { return k_totals; }
    inline uint64_t UTotals( void ) const { return u_totals; }
    
    // total number of keys in the table, same as CountUniqueA(), same as size() accessor for STL map:
    uint64_t size( void ) const;
    
    void Clear( void );
    void Audit( void ) const;
    void BuildRCHisto( map< uint64_t, uint64_t > & rchisto ) const;
};

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

class DleftBase {
protected:
    fis_lock_t glock;
    uint32_t keyIdxOffset;
    char * name;
    IndexedSetBase * base_l;
    IndexedSetBase * base_r;
public:
    void SetName( const char * _name ) {
        if( name ) {
            FREE( name );
        }
        const uint32_t nameLen = strlen( _name );
        name = NULL;
        name = (char *) CALLOC( nameLen + 3, sizeof( char ) );
        assert( name );
        
        sprintf( name, "%s-l", _name );
        base_l->SetName( name );
        sprintf( name, "%s-r", _name );
        base_r->SetName( name );
        
        strcpy( name, _name );
    }
    inline const char * GetName( void ) const { return name; }
    inline void Lock   ( void ) {   LOCK_FUNC( &glock ); }
    inline void Unlock ( void ) { UNLOCK_FUNC( &glock ); }
    void SetHashes( HashWrapper * _hf0, HashWrapper * _hf1 ) {
        // const uint64_t _seed0 = 0xb492b66fbe98f273ULL, const uint64_t _seed1 = 0xc3a5c85c97cb3127ULL
        base_l->SetHash( _hf0 );
        base_r->SetHash( _hf1 );
    }
    uint32_t MaxLoad( void ) const {
        assert( base_l->MaxLoad() == base_r->MaxLoad() );
        return base_l->MaxLoad();
    }
    void Clear( void );
    
    DleftBase  ( void ) { name = NULL;  }
    ~DleftBase ( void ) { FREE( name ); }
};

class DleftIndexedCounters : public DleftBase {
private:
    const uint32_t idxBits;
    const uint32_t wordsPerKey;
    const uint32_t numBuckets;
    const uint64_t hashMask;

    IndexedCounters * l;
    IndexedCounters * r;
    
    map< multi_word, uint64_t > a_over_uniq;
    map< multi_word, uint64_t > k_over_uniq;
    map< multi_word, uint64_t > u_over_uniq;
    uint64_t a_over_total;
    uint64_t k_over_total;
    uint64_t u_over_total;
    
    uint64_t a_totals;
    uint64_t k_totals;
    uint64_t u_totals;
    uint64_t a_unique;
    uint64_t k_unique;
    uint64_t u_unique;
    
    uint32_t InsertKey( const uint64_t * k );
    void IncCountByKeyOverflow( const uint64_t * k, const uint32_t arc, const uint32_t krc, const uint32_t urc );
public:
    DleftIndexedCounters( const uint32_t _idxBits, const uint32_t _wordsPerKey );
    ~DleftIndexedCounters( void );
    
    // the interface to the counters:
    // ... counts[ (k)ey ].allmem += arc
    // ... counts[ (k)ey ].kernel += krc
    // ... counts[ (k)ey ].user   += urc
    void IncCountByKey( const uint64_t * k, const uint32_t arc, const uint32_t krc, const uint32_t urc );
    
    void Audit( void ) const;
    void FreeKeysAndSigs( void );

    // interface to the counts:
    // ... AKU    => (A)ll, (K)ernel, and (U)ser
    // ... Total  => Total reference count
    // ... Unique => Count of unique keys
    void AccumCounts( void );
    inline uint64_t AUnique( void ) const {
        return a_unique;
    }
    inline uint64_t KUnique( void ) const {
        return k_unique;
    }
    inline uint64_t UUnique( void ) const {
        return u_unique;
    }
    inline uint64_t ATotals( void ) const {
        return a_totals;
    }
    inline uint64_t KTotals( void ) const {
        return k_totals;
    }
    inline uint64_t UTotals( void ) const {
        return u_totals;
    }
    void BuildRCHisto( map< uint64_t, uint64_t > & rchisto ) const;
    inline uint64_t NumOverflows( void ) const {
        return a_over_uniq.size();
    }
    void PreLoad( const uint32_t load ) {
        l->PreLoad( load );
        r->PreLoad( load );
    }
    void ClearPreLoad( void ) {
        l->ClearPreLoad();
        r->ClearPreLoad();
    }
    void Clear( void ) {
        a_over_uniq.clear();
        k_over_uniq.clear();
        u_over_uniq.clear();
        l->Clear();
        r->Clear();
    }
    
    double Load( void ) const;
};

#endif












